package MyDFS;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 *     所有数字（包括目标数）都是正整数。
 *     解集不能包含重复的组合。
 *
 * 示例 1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 */
public class Leetcode0040 {
    public static List<List<Integer>> combinationSum2(int[] nums, int target) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }
        Arrays.sort(nums);

        List<Integer> path = new ArrayList<>();

        boolean[] used = new boolean[len];
        for(int i=0 ;i<len; i++){
            if(nums[i] > target){
                used[i] = true;
            }
        }

        // last 上一个值
        dfs(nums, len, target, 0, path, used, res, -1);
        return res;
    }

    private static void dfs(int[] nums, int len, int target, int total,
                            List<Integer> path, boolean[] used,
                            List<List<Integer>> res, int last) {
        if(total > target){
            return;
        }
        if (total == target) {
            // 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
            res.add(path);
            System.out.println(path.toString());
            return;
        }

        for (int i = 0; i < len; i++) {
            if(!used[i] && total + nums[i] <= target && (last <0 || i > last)){
                // 1、每一次尝试都创建新的变量表示当前的"状态"
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);

                boolean[] newUsed = new boolean[len];
                System.arraycopy(used, 0, newUsed, 0, len);
                newUsed[i] = true;

                dfs(nums, len, target, total + nums[i], newPath, newUsed, res, i);

                // 2、无需回溯
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,5,4,4};
        int target = 8;
        combinationSum2(nums, target);
        System.out.println(Integer.valueOf(5));
    }
}
